package com.xiaoqinag.ds;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
import java.util.concurrent.ThreadLocalRandom;

public class SkipList<K, V> {

    private static final int MAX_LEVEL = 10;

    private Node[] head;
    private Node[] tail;

    private volatile int level;
    private final Comparator comparer;

    private int size;

    public SkipList() {
        head = new Node[MAX_LEVEL];
        tail = new Node[MAX_LEVEL];
        for (int i = 0; i < MAX_LEVEL; i++) {
            tail[i] = new Node<>(Integer.MAX_VALUE, Integer.MAX_VALUE, i, null);
            head[i] = new Node<>(0, 0, i, tail[i]);
            if (i != 0) {
                tail[i].down = tail[i - 1];
                head[i].down = head[i - 1];
            }
        }
        comparer = Comparator.comparingInt(Object::hashCode);
        level = 0;
    }

    public V add(V val) {
        return put((K) val, val);
    }

    public V put(K key, V val) {
        return put(key, val, false);
    }

    private V put(K key, V val, boolean onlyIfAbsent) {
        return doPutIfAbsent(key, val, getRandomLevel(), onlyIfAbsent);
    }

    private V doPutIfAbsent(K key, V val, int level, boolean onlyIfAbsent) {
        int newLevel = this.level > level ? this.level : level;

        Node curr = head[newLevel];
        Node newNode = generateNode(key, val, level);
        Node old = new Node();
        this.level = newLevel;
        boolean flag = true;

        while (curr != null && newNode != null && curr.next != null) {
            Node next = curr.next;
            if (comparer.compare(curr.key, newNode.key) == 0) {
                old = curr;
                if (onlyIfAbsent) {
                    return (V) old.value;
                }
                old.value = val;
                curr = curr.down;
            } else if (comparer.compare(curr.key, key) < 0
                    && comparer.compare(next.key, key) > 0) {
                //插入节点
                curr.next = newNode;
                newNode.next = next;

                if (flag) {
                    size++;
                }
                flag = false;
                //向下插入down节点
                newNode = newNode.down;
                curr = curr.down;
            } else {
                curr = next;
            }
        }
        return (V) old.value;
    }

    public Node get(K k) {
        return doGet(k);
    }

    private Node doGet(K key) {
        assert key != null;
        Node curr = head[level];
        while (curr != null && curr.next != null) {
            if (comparer.compare(curr.key, key) == 0) {
                return curr;
            } else if (comparer.compare(curr.next.key, key) <= 0) {
                curr = curr.next;
            } else {
                curr = curr.down;
            }
        }
        return null;
    }

    public int size() {
        return size;
    }

    static class Node<K, V> {
        K key;
        V value;

        int level;
        Node next;
        Node down;


        public Node() {
            this(null, null);
        }

        public Node(K key, V value) {
            this(key, value, 0);
        }

        public Node(K key, V value, int level) {
            this(key, value, level, null);
        }

        public Node(K key, V value, int level, Node next) {
            this.key = key;
            this.value = value;
            this.level = level;
            this.next = next;
        }

        public Node(K key, V value, int level, Node next, Node down) {
            this.key = key;
            this.value = value;
            this.level = level;
            this.next = next;
            this.down = down;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "key=" + key +
                    ", value=" + value +
                    '}';
        }
    }

    /**
     * 生成节点，包括down节点记录
     *
     * @param key
     * @param val
     * @param level
     * @return
     */
    public Node<K, V> generateNode(K key, V val, int level) {
        Node node = new Node<>(key, val, level);
        Node curr = node;
        while (level > 0) {
            curr.down = new Node<>(key, val, --level);
            curr = curr.down;
        }
        return node;
    }

    public static int getRandomLevel() {
        return ThreadLocalRandom.current().nextInt(MAX_LEVEL);
    }


    @Override
    public String toString() {
        return super.toString();
    }
}
